ראיון עורך כשעתיים, חלק ראשון חברתי, חלק שני שאלות תאורטיות
שאלות מתוך הראיון
Given a matrix, check whether it’s Magic Square or not. A Magic Square is a n x n matrix of the distinct elements from 1 to n2 where the sum of any row, column, or diagonal is always equal to the same number.
1. יש 2 רשימות מקושרות. לבדוק האם יש איבר משותף. למצוא אותו לכתוב קוד. בסיבוכיות זמן ומקום מינימאליות.
2. לבנות class לשמירת נתונים בצורה key->value. עם מתודות set,get,reset. reset אמור להגדיר כל האיברים לאותו ערך תוך О(1). גם set,get אמורים לעבוד בО(1). מתודה init(n) בO(n)
תשובות
הוסף תשובה
|
לצפיה בתשובות
מרץ 2022
יש להגדיר משתנים כמו timestamp ו-default_value. כל פעם כשמוסיפים איבר חדש יש לקדם את timestamp ולשמור את ערכו יחד עם האיבר. ב-reset יש לשנות default_value ולשמור timestamp שלו, זה O(1). ב-get יש לבדוק timestamp של איבר, להשוות אותו עם timestamp של default_value ולהחזיר את החדש יותר.
שאלו שאלה על 9 מטבעות. 8 זהות במשקלן ואחת שוקלת יותר. מה הדרך הנכונה ביותר לשקילה עם מאזניים על מנת למצוא את המטבע השונה במינימום שקילות.
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2022
צריך מסקימום 3 שקילות (רק שקילה אחת במקרה הטוב):
שקילה ראשונה: מטבעות 1-4 על כף מאזניים אחת, מטבעות 5-8 על כף שנייה. אם המאזניים מאוזנות אז מטבע מספר 9 הוא הכבד יותר, אם לא ממשיכים:
שקילה שנייה: לוקחים את הרביעיה הכבדה יותר ומפצלים אותה לשניים-שניים על המאזניים.
שקילה שלישית: לוקחים את זוג המטבעות הכבד יותר ומפצלים אותו למטבעות בודדים על המאזניים, וכך נגלה את המטבע הכבד ביותר.
מרץ 2022
אפשר לעשות תמיד ב2 שקילות.
לוקחים את מטבע 1-3 ואת מטבע 4-6, אם הן מאוזנות אז המטבע המזויף נמצא ב7-9. בסוף עושים עוד שקילה אחת עם ה3 מטבעות שנשאר. אם מאוזן המטבע שנותר בחוץ הוא המזויף. ככה תמיד מוצאים את התשובה ב2 שקילות.
- שאלות בנושא של מערכות הפעלה - לדוגמא מקביליות של חוטים,מנעולים וסנכרון בין תהליכים.
- שאלות בנושאים כללים - מציאת ערך של האיבר החסר במערך, ושל שני איברים חסרים במערך - מערך שמכיל N-1 איברים מתוך טווח של 1...N
תשובות
הוסף תשובה
|
לצפיה בתשובות
נובמבר 2021
לגבי מספר אחד פיתרון קל זה סכום סדרה חשבונית ואז לחסר את איברי המערך
לגבי שני מספרים מה שעולה לי זה N! ואז לחלק את כל איברי המערך ולעשות את מה שעשינו עם מספר 1.
אז יש לנו 2 משוואת עם 2 נעלמים ( לא בטוח שזה הכי אופטימלי)
ינואר 2022
יש פתרון כללי (לגבי נעלם אחד, לגבי שני נעלמים, 3 נעלמים וכו').
מגדירים וקטור בגודל N+1 (+1 כי הטווח 1..N מתחיל מ1 ולא מאפס) ומאתחלים את כל הוקטור בשקר (FALSE). עוברים על המערך בלולאה ומכניסים אמת (TRUE) לתוך התאים שהאינדקס שלהם נמצא במערך המספרים:
v[arr[i] = true;
לאחר מכן מריצים לולאה נוספת שרצה על הוקטור ומדפיסים את התאים שיש בהם שקר.
ראיון לתפקיד 
